1. Field of the invention
The present invention relates to communication between electronic devices and more particularly to a method and apparatus for detecting errors in the transmission of digital data.
2. Background of the Invention
In large digital systems, the authenticity of signals which convey the status of one subsystem to another is particularly important for error free operation of the system. Noise is often introduced into digital computer environments both from external sources as well as from switching transients that may occur within a digital device. Similarly, noise is often introduced into telecommunication lines, such noise often being environmentally produced, either by man or nature. In digital systems in particular, such noise may be interpreted as data or instructions and may lead to incorrect results or catastrophic failure of the system. It is therefore important to be able to verify that a transmitted signal has in fact been correctly received.
At least three types of circuits and methods have been used in the prior art to ascertain that a signal has been accurately transmitted. In one method, the signal which needs to be verified is transmitted over two wires instead of only one wire. Thus a simple comparison of both signals at the receiving end can be made. If the received signals differ an error in transmission has occurred and appropriate corrective action can be implemented.
Oftentimes a given system will tend to pull a signal one way or the other. That is, it may tend to favor the introduction of errors that for example, make signals logical 0 when in fact the signal should be logical 1, or vice versa. Such systems can be compensated for in an enhancement to the basic two wire system by taking the signal it is wished to transmit, and transmitting in parallel with it, an inverted version of the signal. Both such systems require the use of an additional line for the transmission of the extra signal.
Another method known in the art is the transmission of a parity signal, which is used when several signals are transmitted from one device to another. The bits of these signals can be added to generate a parity signal corresponding to whether the bits add up to an odd or even number, and the parity signal transmitted along with the signals it is desired to verify. If an odd number of these signals are in error, the transmission error can be detected. This also often requires use of a separate dedicated line for transmission of the parity bit or signal.
Packaging constraints often prevent the use of conventional error detection/correction schemes (such as parity lines), because these schemes require additional wires to incorporate redundancy and there is often simply no room available for this purpose.
In the third type of error checking devices, only a single wire is used but additional error codes are added. In these systems, a data stream is divided into a sequential series of periodic time slices. An error checking code is added to the data within each time slice, which is transmitted along with the original data. This requires a faster transmission rate for the encoded signal to accommodate the added information.
These systems have the inherent disadvantage of degrading the performance of the system in which they are incorporated. For example, in systems where the data remains stable over periods of time that are long relative to the period of the time slice, even though there is no transition of data, a new signal must be sent for each time slice with the code added to it. Thus, circuitry time and overhead must be devoted to such an error checking signal even when the system has no need for error checking.
Furthermore, such systems are not truly asynchronous since both the receiver and transmitter must be set to the same time slice. Additionally, the selection of the length of the time slice is usually constrained.
In U.S. Pat. No. 4,020,282, entitled HIGH DENSITY DATA PROCESSING SYSTEM, a data processing system applicable to high density magnetic recording and data transmission wherein digital data is translated into multi-level zero average words which occupy a greater number of time slots than the bits of the digital data which they represent, is described. The words having increased power density in the signal spectra represent the difference between different words. After recording or transmission, the signals are detected and decoded in accordance with the amplitude characteristics of samples of the detected signals occurring during time slots which are occupied by samples, the sum of which is equal to zero. More particularly, the system converts every four bit binary number into a sequence of 6 bits having equal number of ones and zeros.
In U.S. Pat. No. 4,007,421, entitled CIRCUIT FOR ENCODING AN ASYNCHRONOUS BINARY SIGNAL INTO A SYNCHRONOUS CODED SIGNAL, a system is described in which each asynchronous transition is encoded into a two bit binary code. Successive intervals of an asynchronous binary signal are examined for the occurrence of transitions and each transition is encoded into a two bit binary code word. The occurrence of two transitions within a predetermined interval of time indicates that the asynchronous signal is distorted. A first code word is generated in response to the first transition to indicate to remote decoding apparatus the occurrence of the first transition within the interval of actual occurrence. A second code word is generated in response to the second transition to indicate to the remote decoding apparatus the occurrence of the second transition in an interval immediately subsequent to the interval in which the second transition actually occurred. Polarity information is periodically transmitted to the decoding apparatus to ensure that the polarity of the asynchronous signal reproduced by the decoding apparatus is the same as the polarity of the original asynchronous signal.
In U.S. Pat. No. 3,938,085, entitled TRANSMITTING STATION AND RECEIVING STATION FOR OPERATING WITH A SYSTEMATIC RECURRENT CODE, a transmitting station is described which comprises coding means, including a shift register having L stages, where L is the length of the code, for delivering continuation and repetition bit trains, each of which comprises information bits including at least L message bits as well as the parity bits associated with the information bits. In the case of a continuation bit train, the L message bits are supplied by a data source, in the case of a repetition bit train, they are fed back to the coding means from the shift register. In the receiving station, the decoding of messages bits is a conventional decoding in accordance with the code where a continuation bit train is concerned, but also takes into account the previously decoded value where a repetition bit train is concerned. The trains may be identified by means of prefixes of N.sub.1 bits, in which case, each bit train comprises (N.sub.1 +L) information bits.
In U.S. Pat. No. 3,909,784 issued Sept. 30, 1975 to Raymond et al., entitled INFORMATION CODING WITH ERROR TOLERANT CODE, information is expressed in the form of pulses which are arranged in accordance with the equation: M.sub.n =xn+T where n is the code number, M is the quantity of pulses per code number, T is the negative tolerance of pulse count, and x is the sum of one pulse the positive tolerance and the negative tolerance of pulse count. The redundant pulses are added in order to withstand loss of T pulses or gain of x-1 pulses.